package week02

// 200. 岛屿数量
// https://leetcode-cn.com/problems/number-of-islands/

// 只要遍历就行，深度优先、广度优先都可以
// 出边可以由方向确定，所以可以不构造图

func numIslands(grid [][]byte) int {
	var ans = 0
	var visit = make(map[int]bool)
	for row := range grid {
		for col := range grid[row] {
			if grid[row][col] == '1' && !visit[hash(grid, row, col)] {
				dfs(grid, row, col, visit)
				ans++
			}
		}
	}
	return ans
}

func dfs(grid [][]byte, row, col int, visit map[int]bool) {
	visit[hash(grid, row, col)] = true
	for i := range dx {
		nRow := row + dx[i]
		nCol := col + dy[i]

		if nRow < 0 || nRow >= len(grid) || nCol < 0 || nCol >= len(grid[nRow]) {
			continue
		}
		if grid[nRow][nCol] == '1' && !visit[hash(grid, nRow, nCol)] {
			dfs(grid, nRow, nCol, visit)
		}
	}
}

func hash(grid [][]byte, row, col int) int {
	return row + len(grid) * col
}

var dx = [4]int{0, 1, 0, -1}
var dy = [4]int{1, 0, -1, 0}

